package top.fengleifeng.question;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;

/**
 * @author : fengelfeing
 * @version V1.0
 * @Project: leetcode-test
 * @Package : top.fengleifeng.question
 * @Description: 给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
 * <p>
 * 每次转换只能改变一个字母。 转换过程中的中间单词必须是字典中的单词。 说明:
 * <p>
 * 如果不存在这样的转换序列，返回 0。 所有单词具有相同的长度。 所有单词只由小写字母组成。 字典中不存在重复的单词。 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。 示例 1:
 * <p>
 * 输入: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
 * <p>
 * 输出: 5
 * <p>
 * 解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。 示例 2:
 * <p>
 * 输入: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log"]
 * <p>
 * 输出: 0
 * <p>
 * 解释: endWord "cog" 不在字典中，所以无法进行转换。 通过次数75,110提交次数167,918
 * <p>
 * <p>
 * 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/word-ladder 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Date: 2020年11月05日4:29 下午
 */
public class Num127单词接龙 {

    class Solution {

        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            //先判断能不能变
            Set<String> wordSet = new HashSet<>(wordList);
            if (wordSet.size() == 0 || !wordSet.contains(endWord)) {
                return 0;
            }
            wordSet.remove(beginWord);
            Queue<String> queue = new LinkedList<>();
            queue.offer(beginWord);
            Set<String> visited = new HashSet<>();
            visited.add(beginWord);
            int step = 1;
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    String str = queue.poll();
                    int length = str.length();
                    char[] now = str.toCharArray();
                    for (int j = 0; j < length; j++) {
                        char nowChar = now[j];
                        for (char k = 'a'; k <= 'z'; k++) {
                            if (k == nowChar) {
                                continue;
                            }
                            now[j] = k;
                            String newString = String.valueOf(now);
                            if (wordSet.contains(newString)) {
                                if (newString.equals(endWord)) {
                                    return step + 1;
                                }
                                if (!visited.contains(newString)) {
                                    queue.add(newString);
                                    visited.add(newString);
                                }
                            }
                        }
                        now[j] = nowChar;
                    }
                }
                step++;
            }
            return 0;
        }
    }

    public static void main(String[] args) {
        String beginWord = "hit";
        String endWord = "cog";
        List<String> list = new LinkedList<>();// ["hot","dot","dog","lot","log","cog"]
        list.add("hot");
        list.add("dot");
        list.add("dog");
        list.add("lot");
        list.add("log");
        list.add("cog");
        int i = new Num127单词接龙().new Solution().ladderLength(beginWord, endWord, list);
        System.out.println(i);
    }
}
